/*
 * @lc app=leetcode.cn id=207 lang=typescript
 *
 * [207] 课程表
 */

// @lc code=start

//  思路：BFS
//  利用出入度的思想，入度为0的表示没有依赖此节点的，先加入队列
//  遍历队列每一个结点，出队列，通过map找当前节点依赖的节点，修改入度
//  count计算出队列的个数，与课程一致则ok
//  其他方法：https://labuladong.github.io/algo/2/20/35/

//  复杂度：O(n) O(n)

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    // 入度数组
    const inArr = new Array(numCourses).fill(0)
    const map = new Map()
    prerequisites.forEach(preArr => {
        inArr[preArr[0]]++  // 入度+1
        if (map.has(preArr[1])) {
            map.get(preArr[1]).push(preArr[0]) // 有则添加
        } else {
            map.set(preArr[1], [preArr[0]])
        }
    })
    // 找入度为0的点加入队列
    const queue: any = []
    inArr.forEach((item, index) => {
        if (!item) queue.push(index)
    })
    // 开始遍历
    let count = 0
    while (queue.length) {
        const curr = queue.shift()
        count++
        const currToArr = map.get(curr)
        if (currToArr && currToArr.length) {
            // 减少当前节点相邻节点的入度
            for (let i = 0; i < currToArr.length; i++) {
                inArr[currToArr[i]]--
                if (!inArr[currToArr[i]]) {
                    queue.push(currToArr[i])
                }
            }
        }
    }
    return count === numCourses
};
// @lc code=end

console.log(canFinish(2, [[1, 0]]))
console.log(canFinish(2, [[1, 0], [0, 1]]))
